1. Field of the Invention
This invention relates in general to the field of microelectronics, and more particularly to a technique for executing a carryless multiplication.
2. Description of the Related Art
Most communications today of any importance are communicated with some form of security feature. The resources available for secure communications range from simple authenticated signatures all the way up through a hashed enciphered message using symmetric key encryption techniques. And one of the modes of operation for symmetric key encryption that is becoming more prevalent is the so-called Galois/Counter Mode (GCM) which provides for both encryption and authentication of a message.
GCM mode is a combination of the well-known counter mode of encryption with the more recently developed Galois mode of authentication. In GCM mode, Galois field multiplication is used for authentication. And while it is beyond the scope of the present application to provide an in-depth discussion of Galois field multiplication, it is sufficient to note that carryless multiplication is the first step that one employs when performing a Galois field multiplication.
Carryless multiplication is also known as binary polynomial multiplication and is the mathematical operation of computing the product of two operands without generating or propagating carries. In fact, INTEL® has provided an instruction, PCLMULQDQ, that directs an x86-compatible microprocessor to perform this very function.
Consequently, as microprocessor designers develop modifications to existing designs to provide more advanced features, carryless multiplication must be considered. This is an operation that is straightforward, but as one skilled in the art will appreciate, requires a significant amount of hardware to implement. For example, consider that a 64-bit carryless multiplication operation comprises the generation of 64 partial products which much then be exclusive-ORed together in order to yield a final 128-bit result. Currently, there is no unit or logic allocated within most microprocessor designs today that will perform this function, however most microprocessors have one or more multiplication units for performing ordinary multiplication.
Yet, as one skilled in the art will appreciate, many improvements have been developed in more recent years that allow present day multiplication units to perform much faster that would otherwise be provided for. For instance, Booth encoding is an extremely common technique that is used to cut the number of partial products in a multiplication by half Wallace trees are also commonly employed as the elements used to add together the partial products that are generated via Booth encoding.
And while very efficient from a performance perspective, the techniques noted above inherently generate and propagate carry bits. As a result, the hardware within a present day multiplication unit is entirely unsuitable for use in carryless multiplications.
The present inventor has noted this disadvantage, and others, and observes that it is desirable in the art to maximize the common use of hardware in order to reduce power consumption and device footprint, and to increase the reliability of a part. In addition, common hardware use is desirable from a debug and testing perspective as well in that well-known elements are being used for a different function.
Therefore, what is needed is an apparatus and method for performing a carryless multiplication operation in a processor or other device which maximizes the use of common hardware elements.
In addition, what is needed is a multiplication unit that is capable of performing both ordinary and carryless multiplication, where modifications to the unit are negligible.